<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>数字增加，删除，得到最大，最小数</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="数字增加删除得到最大最小数">数字增加，删除，得到最大，最小数</h1>
<h1 id="1-lc-402-remove-k-digits">1. LC 402. Remove K Digits</h1>
<ul>
<li><a href="https://leetcode.com/problems/remove-k-digits/">https://leetcode.com/problems/remove-k-digits/</a></li>
</ul>
<p>Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.</p>
<pre><code><code><div>Note:
The length of num is less than 10002 and will be ≥ k.
The given num does not contain any leading zero.
Example 1:

Input: num = &quot;1432219&quot;, k = 3
Output: &quot;1219&quot;
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Example 2:

Input: num = &quot;10200&quot;, k = 1
Output: &quot;200&quot;
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Example 3:

Input: num = &quot;10&quot;, k = 2
Output: &quot;0&quot;
Explanation: Remove all the digits from the number and it is left with nothing which is 0.
</div></code></code></pre>
<p>我的解法， 比较费劲</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> collections <span class="hljs-keyword">import</span> deque

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">removeKdigits</span><span class="hljs-params">(self, num: str, k: int)</span> -&gt; str:</span>
        <span class="hljs-keyword">if</span> k &gt;= len(num):
            <span class="hljs-keyword">return</span> <span class="hljs-string">"0"</span>
        
        q = deque(num)
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">helper</span><span class="hljs-params">(q)</span>:</span>
            <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> q:
                <span class="hljs-keyword">return</span>
            
            s = []
            <span class="hljs-keyword">while</span> q:
                <span class="hljs-comment">#print(f"q={q}")</span>
                c = q[<span class="hljs-number">0</span>]
                <span class="hljs-keyword">if</span> (<span class="hljs-keyword">not</span> s) <span class="hljs-keyword">or</span> (s <span class="hljs-keyword">and</span> s[<span class="hljs-number">-1</span>] &lt;= c):
                    q.popleft()
                    s.append(c)
                <span class="hljs-keyword">else</span>:
                    <span class="hljs-keyword">break</span>
            <span class="hljs-comment">#print(f"s={s} q={q}")</span>
            <span class="hljs-keyword">if</span> s:
                s.pop()
                <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> s:
                    <span class="hljs-keyword">while</span> q <span class="hljs-keyword">and</span> q[<span class="hljs-number">0</span>] == <span class="hljs-string">"0"</span>:
                        q.popleft()
                <span class="hljs-keyword">else</span>:
                    <span class="hljs-keyword">while</span> s:
                        q.appendleft(s.pop())
            <span class="hljs-keyword">else</span>:
                q.pop()
            <span class="hljs-comment">#print(f"q2={q}")</span>
        
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(k):
            helper(q)
        
        <span class="hljs-keyword">return</span> <span class="hljs-string">""</span>.join(q) <span class="hljs-keyword">if</span> q <span class="hljs-keyword">else</span> <span class="hljs-string">"0"</span>       
</div></code></pre>
<p>别人的解法</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">removeKdigits</span><span class="hljs-params">(self, num: str, k: int)</span> -&gt; str:</span>
        s = []
        <span class="hljs-keyword">for</span> c <span class="hljs-keyword">in</span> num:
            <span class="hljs-keyword">while</span> s <span class="hljs-keyword">and</span> k <span class="hljs-keyword">and</span> c &lt; s[<span class="hljs-number">-1</span>]:
                s.pop()
                k -= <span class="hljs-number">1</span>
            s.append(c)
    
        <span class="hljs-keyword">while</span> k:
            s.pop()
            k -= <span class="hljs-number">1</span>
    
        <span class="hljs-keyword">return</span> <span class="hljs-string">""</span>.join(s).lstrip(<span class="hljs-string">"0"</span>) <span class="hljs-keyword">or</span> <span class="hljs-string">"0"</span>
    
</div></code></pre>
<h1 id="2-lc-484-find-permutation">2. LC 484. Find Permutation</h1>
<ul>
<li><a href="https://leetcode.com/problems/find-permutation/">https://leetcode.com/problems/find-permutation/</a></li>
</ul>
<p>y now, you are given a secret signature consisting of character 'D' and 'I'. 'D' represents a decreasing relationship between two numbers, 'I' represents an increasing relationship between two numbers. And our secret signature was constructed by a special integer array, which contains uniquely all the different number from 1 to n (n is the length of the secret signature plus 1). For example, the secret signature &quot;DI&quot; can be constructed by array [2,1,3] or [3,1,2], but won't be constructed by array [3,2,4] or [2,1,3,4], which are both illegal constructing special string that can't represent the &quot;DI&quot; secret signature.</p>
<p>On the other hand, now your job is to find the lexicographically smallest permutation of [1, 2, ... n] could refer to the given secret signature in the input.</p>
<pre><code><code><div>Example 1:
Input: &quot;I&quot;
Output: [1,2]
Explanation: [1,2] is the only legal initial spectial string can construct secret signature &quot;I&quot;, where the number 1 and 2 construct an increasing relationship.

Example 2:
Input: &quot;DI&quot;
Output: [2,1,3]
Explanation: Both [2,1,3] and [3,1,2] can construct the secret signature &quot;DI&quot;, 
but since we want to find the one with the smallest lexicographical permutation, you need to output [2,1,3]
</div></code></code></pre>
<p>这道题虽然是middle难度， 还是比较难找到思路的。</p>
<p>my solution, 从右往左遍历字符串s,  主要是对D的处理，把连续的D转换为 当前candidates连续的从最大数开始的字串。例如s = &quot;DIDD&quot;, 从右往左遍历。</p>
<ul>
<li>IDD -&gt; 543</li>
<li>D -&gt; 21</li>
</ul>
<p>我的解法应该和官方答案的第二种解法 #2 Reversing the subarray 是一样的。</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findPermutation</span><span class="hljs-params">(self, s: str)</span> -&gt; List[int]:</span>
        n = len(s)
        s2 = list(s)
        candidates = list(range(<span class="hljs-number">1</span>, n+<span class="hljs-number">2</span>))
        ans = deque()
        
        <span class="hljs-keyword">while</span> s2:
            D = <span class="hljs-number">0</span>
            <span class="hljs-keyword">while</span> s2 <span class="hljs-keyword">and</span> s2[<span class="hljs-number">-1</span>] == <span class="hljs-string">"D"</span>:
                s2.pop()
                D += <span class="hljs-number">1</span>
            tmp = deque()
            <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(D):
                tmp.append(candidates.pop())
            <span class="hljs-keyword">if</span> s2:
                tmp.append(candidates.pop())
                s2.pop()
            <span class="hljs-keyword">else</span>:
                tmp.append(candidates.pop())
            ans = tmp + ans
        <span class="hljs-keyword">if</span> candidates:
            ans.appendleft(candidates.pop())
        <span class="hljs-keyword">return</span> ans
</div></code></pre>
<h1 id="3-lc-316-remove-duplicate-letters">3. LC 316. Remove Duplicate Letters</h1>
<ul>
<li><a href="https://leetcode.com/problems/remove-duplicate-letters/">https://leetcode.com/problems/remove-duplicate-letters/</a></li>
</ul>
<p>Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.</p>
<p>Note: This question is the same as 1081: <a href="https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/">https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/</a></p>
<pre><code><code><div>Example 1:

Input: s = &quot;bcabc&quot;
Output: &quot;abc&quot;

Example 2:

Input: s = &quot;cbacdcbc&quot;
Output: &quot;acdb&quot;
</div></code></code></pre>
<p>官方答案</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">removeDuplicateLetters</span><span class="hljs-params">(self, s)</span> -&gt; int:</span>

        stack = []

        <span class="hljs-comment"># this lets us keep track of what's in our solution in O(1) time</span>
        seen = set()

        <span class="hljs-comment"># this will let us know if there are no more instances of s[i] left in s</span>
        last_occurrence = {c: i <span class="hljs-keyword">for</span> i, c <span class="hljs-keyword">in</span> enumerate(s)}


        <span class="hljs-keyword">for</span> i, c <span class="hljs-keyword">in</span> enumerate(s):

            <span class="hljs-comment"># we can only try to add c if it's not already in our solution</span>
            <span class="hljs-comment"># this is to maintain only one of each character</span>
            <span class="hljs-keyword">if</span> c <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> seen:
                <span class="hljs-comment"># if the last letter in our solution:</span>
                <span class="hljs-comment">#    1. exists</span>
                <span class="hljs-comment">#    2. is greater than c so removing it will make the string smaller</span>
                <span class="hljs-comment">#    3. it's not the last occurrence</span>
                <span class="hljs-comment"># we remove it from the solution to keep the solution optimal</span>
                <span class="hljs-keyword">while</span> stack <span class="hljs-keyword">and</span> c &lt; stack[<span class="hljs-number">-1</span>] <span class="hljs-keyword">and</span> i &lt; last_occurrence[stack[<span class="hljs-number">-1</span>]]:
                    seen.discard(stack.pop())
                seen.add(c)
                stack.append(c)
        <span class="hljs-keyword">return</span> <span class="hljs-string">''</span>.join(stack)

</div></code></pre>
<p>我的答案</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">removeDuplicateLetters</span><span class="hljs-params">(self, s: str)</span> -&gt; str:</span>
        last = {}
        <span class="hljs-keyword">for</span> i,c <span class="hljs-keyword">in</span> enumerate(s):
            last[c] = i
            
        q = []
        <span class="hljs-keyword">for</span> i,c <span class="hljs-keyword">in</span> enumerate(s):
            <span class="hljs-keyword">if</span> c <span class="hljs-keyword">in</span> q <span class="hljs-keyword">and</span> c &lt; q[<span class="hljs-number">-1</span>]:  <span class="hljs-comment"># 这个地方可以改成 if c in q: continue 不需要判断 c &lt; q[-1]</span>
                <span class="hljs-keyword">continue</span>
                
            <span class="hljs-keyword">while</span> q <span class="hljs-keyword">and</span> q[<span class="hljs-number">-1</span>] &gt;= c:
                <span class="hljs-keyword">if</span> i<span class="hljs-number">-1</span> &lt; last[q[<span class="hljs-number">-1</span>]]:
                    q.pop()
                <span class="hljs-keyword">else</span>:
                    <span class="hljs-keyword">break</span>
            
            q.append(c)
        <span class="hljs-keyword">return</span> <span class="hljs-string">""</span>.join(q )
    
</div></code></pre>

    </body>
    </html>